package leetcode;

/**
 * Created by baoyunfeng on 2019/8/5.
 * <p>
 * https://leetcode.com/problems/longest-palindromic-substring/submissions/
 * Time Limit Exceeded
 * <p>
 * 思路1：使用int[][]存储转换后的数据，之后遍历输出
 * 思路2：预估转换后的位置，直接匹配使用
 */
public class Longest_Palindromic_Substring {

    public static void main(String args[]) {
//        System.out.print(longestPalindrome("abcda"));
        System.out.print(longestPalindrome
                ("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));
    }

    public static String longestPalindrome(String s) {
//        int num[][] = new int[s.length()][s.length()];
        String longest = "";
        for (int i = 0; i < s.length(); i++) {
            for (int j = i; j < s.length(); j++) {
                boolean flag = false;
                int mid = i + (j - i + 1) / 2;
                for (int k = i; k <= mid; k++) {
                    if (s.charAt(k) != s.charAt(j - (k - i))) {
                        flag = true;
                        break;
                    }
                }
                if (!flag && j - i + 1 > longest.length()) {
                    longest = "";
                    for (int k = i; k <= j; k++) {
                        longest += s.charAt(k);
                    }
                }
            }
        }


        return longest;
    }


    public static String longestPalindrome2(String s) {

        String maxStr = "";
        for (int i = 0; i < s.length() * 2 - 1; i++) {
            if (i % 2 == 0) {
                int startIndex = i / 2;
                int gap = 0;
                while (startIndex - gap >= 0 && startIndex + gap < s.length()) {
                    if (s.charAt(startIndex - gap) == s.charAt(startIndex + gap)) {
                        gap++;
                    } else {
                        break;
                    }
                }
                gap--;
                if (gap * 2 + 1 >= maxStr.length()) {
                    maxStr = s.substring(startIndex - gap, startIndex + gap + 1);
                }
            } else {
                int startIndex = i / 2;
                int gap = 0;
                while (startIndex - gap + 1 >= 0 && startIndex + gap < s.length()) {
                    if (s.charAt(startIndex - gap + 1) == s.charAt(startIndex + gap)) {
                        gap++;
                    } else {
                        break;
                    }
                }
                gap--;
                if (gap * 2 >= maxStr.length()) {
                    maxStr = s.substring(startIndex - gap + 1, startIndex + gap + 1);
                }
            }
        }
        return maxStr;
    }
}
